#include "Node.cc"
//  virtual -> override 重定义, 动态绑定
// 没有virtual -> hid 隐藏, 不动态绑定
class Tree
{
protected:
    PNode root;
    void helpPrePrint(PNode);
    void helpdestroy(PNode&);
public:
    Tree() : root(nullptr) { ; }
    Tree(vector<int> nums) : Tree()
    {
        for (auto &num : nums)
            this->insert(num);
    }
    virtual ~Tree();
    virtual PNode insert(int);
    void PrePrint();
};

void Tree::helpPrePrint(PNode node)
{
    if (!node)
        return;
    cout << node->val << " ";
    helpPrePrint(node->l);
    helpPrePrint(node->r);
}

void Tree::helpdestroy(PNode &node)
{
    if(!node)
        return;
    helpdestroy(node->l);
    helpdestroy(node->r);
    delete node;
    node = nullptr;
}

void Tree::PrePrint()
{
    this->helpPrePrint(this->root);
    cout << endl;
}

PNode Tree::insert(int val)
{
    PNode *thisnode = &(this->root);
    while (*thisnode)
    {
        thisnode = rand() % 2 ? &((*thisnode)->r) : &((*thisnode)->l);
    }
    *thisnode = new Node(val);
    return *thisnode;
}

Tree::~Tree(){
    helpdestroy(this->root);
}